// O(N)  10亿
function sqrt1 (num) {
    if (num < 2) {
        return num;
    }
    let i = 1;
    while (i * i <= num) {
        i++;
    }
    return i - 1;
}

// log以2位底n的对数
function sqrt2 (x) {
    if (x === 0) return 0
    let l = 0 // left
    let r = x // right
    let mid
    let res = 0
    while(l <= r) {
        mid = parseInt((l+r)/2)
        if (mid * mid <= x) {
            l = mid + 1
            res = mid
        } else {
            r = mid - 1
        }
    }
    return res
};

function performance (name, cb, count = 100000) {
    console.time(name);
    for (let i = 0; i < count; i++) {
        cb();
    }
    console.timeEnd(name);
}

performance('我们', () => {
    sqrt1(Math.floor(Math.random() * 1000000000));
});

performance('二分', () => {
    sqrt2(Math.floor(Math.random() * 1000000000));
});
